/*
 * @Author: kaikaima
 * @Date: 2021-01-12 21:13:13
 * @LastEditTime: 2021-01-12 22:03:28
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /undefined/home/messi/Data_Structure_and_Algorithm_GIT/Graph/main.h
 */
#ifndef __hhxxttxs_GRAPH__
#define __hhxxttxs_GRAPH__

#include<iostream>
#include<vector>

#define BLACK true
#define WHITE false

/**
 * @description: Tvalue is the parlance of the information(name) in Nodes.
 * @param {*} _a for Node; _b for Tvalue; _c for length(len);
 * @return {*}
 */
template <class Tvalue>
class Graph{
private:
class Node;
class Adj;
    /**
     * @description: (Node*)u->Adj is a linkedlist that contains all the adjoining Nodes of u.
     * @param {*}
     * @return {*}
     */
    class Node{
    public:
        Tvalue name;
        int num=-1;
        Adj* path;
        Node* parent;
        bool color=WHITE;
        Node() {path=parent=NULL;};
        Node(Tvalue _b) {name=_b; path=parent=NULL;};
    };
    class Adj{
    public:
        int len;
        Node* another;
        Adj* next;
        /**
         * @description: use -1 to represent infinity
         * @param {*}
         * @return {*}
         */
        Adj() {next=another=NULL;len=-1;};
        Adj(int _c, Node* _a) {len=_c;next=NULL;another=_a;};
    };
    /**
     * @description: each Node will be connected with head, while some are infinite. 
     * @param {*}
     * @return {*}
     */
    Node* head;
    Node* search(Tvalue _b) const;
    void insert(Node* _a1, Node* _a2, int _c);
    void release (Node* _a);
public:
    Graph() {head=NULL;};
    Graph(Tvalue _b) {head=new Node(_b);};
    Graph(Tvalue _b1, Tvalue _b2, int _c) {
        head=new Node(_b1);
        Node* key=new Node(_b2);
        head->path=new Adj(_c,key);
        key->path=new Adj(_c,head);
    };
    ~Graph();
    void insert(Tvalue _b1, Tvalue _b2, int _c);
    int how_long(Tvalue _b1, Tvalue _b2) const;
};

template <class Tvalue>
typename Graph<Tvalue>::Node* Graph<Tvalue>::search(Tvalue _b) const{
    
};


template <class Tvalue>
void Graph<Tvalue>::insert(Node* _a1, Node* _a2, int _c){
    if(head==NULL){
        head=_a1;
        head->path=new Adj(_c,_a2);
        _a2->path=new Adj(_c,head);
    }
    else{
        Adj* p=head->path;
        while(p!=NULL &&(p->another!=_a1 || p->another!=_a2)) p=p->next;
        if(p==NULL){
            p=new Adj(-1,_a1);
            p->next=new Adj(-1,_a2);
            _a1->path=new Adj(_c,_a2);
        }
        else if(p->another==_a1){
            while()
        }
    }
    
};

template <class Tvalue>
template <class Tvalue>
template <class Tvalue>

#else
//do nothing
#endif